/*
 * @lc app=leetcode.cn id=139 lang=golang
 *
 * [139] 单词拆分
 */

// @lc code=start

func wordBreak(s string, wordDict []string) bool {
	m, n := len(s), len(wordDict)
	wordTomap := make(map[string]struct{})
	for i := 0; i < n; i++ {

		wordTomap[wordDict[i]] = struct{}{}

	}
	res := make([]bool, m+1)
	// for i, _ := range res {
	// 	res[i] = false

	// }
	res[0] = true
	for i := 1; i <= m; i++ {
		for j := 0; j < i; j++ {
			if _, ok := wordTomap[s[j:i]]; ok && res[j] {
				res[i] = true
				break
			}
		}

	}
	return res[m]
}

// @lc code=end
